//二叉搜索树
#ifndef __BINARYSEARCHTREE__HPP
#define __BINARYSEARCHTREE__HPP

#include"BinaryTree.hpp"
#include"../../Algorithm/Sort.hpp"

namespace NgSiuKei {

//构造
template<class TheClass>
binary_tree_node<TheClass> *createBinarySearchTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return nullptr;
    }
    //复制一个树，需要保证构造的树结构不变
    binary_tree_node<TheClass> *newTree = copyTree(tree);
    //获取排序后的参数
    U_L_L nodeNum = getTreeNodeNum(newTree);
    TheClass *array = orderTree(newTree, ORDER_TYPE_PRE);
    bubbleSort(array, nodeNum);
    //根据定义，不能有相同的val
    for(U_L_L i=0; i<nodeNum-1; ++i) {
        if(array[i] == array[i+1]) {
            return nullptr;
        }
    }
    //以中序遍历方式塞入数据
    U_L_L index = 0;
    setVal(newTree, array, index);

    return newTree;
}

//普通二叉树转换成二叉搜索树
template<class TheClass>
void convertToBinarySearchTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return;
    }
    //获取排序后的参数
    U_L_L nodeNum = getTreeNodeNum(tree);
    TheClass *array = orderTree(tree, ORDER_TYPE_PRE);
    bubbleSort(array, nodeNum);
    //根据定义，不能有相同的val
    for(U_L_L i=0; i<nodeNum-1; ++i) {
        if(array[i] == array[i+1]) {
            return;
        }
    }
    //以中序遍历方式塞入数据
    U_L_L index = 0;
    setVal(tree, array, index);
}

//判断是不是二叉搜索树
template<class TheClass>
bool isBST(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return true;
    }
    bool leftIsSmallerThanMain = true;
    bool rightIsBiggerThanMain = true;
    if(nullptr != tree->leftChild) {
        leftIsSmallerThanMain = (tree->leftChild->val < tree->val);
    }
    if(nullptr != tree->rightChild) {
        rightIsBiggerThanMain = (tree->val < tree->rightChild->val);
    }
    return leftIsSmallerThanMain && rightIsBiggerThanMain && isBST(tree->leftChild) && isBST(tree->rightChild);
}

//排序后的数据按中序遍历插入即可得到二叉搜索树
template<class TheClass>
static void setVal(binary_tree_node<TheClass> *tree, TheClass *&array, U_L_L &index) {
    if(nullptr == tree) {
        --index;
        return;
    }
    setVal(tree->leftChild, array, index);
    tree->val = array[++index];
    setVal(tree->rightChild, array, ++index);
}

//查找
template<class TheClass>
bool findVal(binary_tree_node<TheClass> *tree, TheClass val) {
    if(nullptr == tree) {
        return false;
    }
    else if(val == tree->val) {
        return true;
    }
    else if(val < tree->val){
        return findVal(tree->leftChild, val);
    }
    else if(val > tree->val) {
        return findVal(tree->rightChild, val);
    }
    else {
        return false;
    }
}

//查找最大的值
template<class TheClass>
TheClass getMaxVal(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree->rightChild) {
        return tree->val;
    }
    else {
        return getMaxVal(tree->rightChild);
    }
}

//查找最小的值
template<class TheClass>
TheClass getMinVal(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree->leftChild) {
        return tree->val;
    }
    else {
        return getMinVal(tree->leftChild);
    }
}

//插入数据
template<class TheClass>
void insertValToBinarySearchTree(binary_tree_node<TheClass> *&tree, TheClass val) {
    if(findVal(tree, val)) {
        return;
    }
    binary_tree_node<TheClass> *newNode = nullptr;
    if(val < tree->val) {
        if(nullptr == tree->leftChild) {
            newNode = new binary_tree_node<TheClass>;
            newNode->val = val;
            newNode->leftChild = nullptr;
            newNode->rightChild = nullptr;
            tree->leftChild = newNode;
        }
        else {
            insertValToBinarySearchTree(tree->leftChild, val);
        }
    }
    else {
        if(nullptr == tree->rightChild) {
            newNode = new binary_tree_node<TheClass>;
            newNode->val = val;
            newNode->leftChild = nullptr;
            newNode->rightChild = nullptr;
            tree->rightChild = newNode;
        }
        else {
            insertValToBinarySearchTree(tree->rightChild, val);
        }
    }
}

//删除数据
template<class TheClass>
void deleteValFromBinarySearchTree(binary_tree_node<TheClass> *&tree, TheClass val) {
    if(!findVal(tree, val)) {
        return;
    }
    if(val < tree->val) {
        deleteValFromBinarySearchTree(tree->leftChild, val);
    }
    else if(val > tree->val) {
        deleteValFromBinarySearchTree(tree->rightChild, val);
    }
    else {
        //删除操作
        if(nullptr == tree->leftChild && nullptr == tree->rightChild) {
            delete tree;
            tree = nullptr;
        }
        else if(nullptr == tree->leftChild || nullptr == tree->rightChild) {
            //一个后代
            binary_tree_node<TheClass> *tempNode = tree;
            if(nullptr == tree->leftChild) {
                //右
                tree = tree->rightChild;
            }
            else {
                //左
                tree = tree->leftChild;
            }
            delete tempNode;
        }
        else {
            //双后代
            tree->val = getMaxVal(tree->leftChild);
            deleteValFromBinarySearchTree(tree->leftChild, tree->val);
            //下面这样也行
            // tree->val = getMinVal(tree->rightChild);
            // deleteValFromBinarySearchTree(tree->rightChild, tree->val, tree);
        }
    }
}

}

#endif